package com.wcj.sort;

public class 归并排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{23,12,36,451,2,89,78,54,-10,7434234,21321,238924,463535};
        mergeSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void mergeSort(int[] arr){
        int[] tmpArr = new int[arr.length];
        mergeSort(arr,tmpArr,0,arr.length-1);
    }

    private static void mergeSort(int[] arr, int[] tmpArr, int left, int right) {
        if (left < right){
            int center = left + (right - left)/2;
            mergeSort(arr,tmpArr,left,center);
            mergeSort(arr,tmpArr,center + 1,right);
            merge(arr, tmpArr, left, center +1,right);
        }
    }

    private static void merge(int[] arr, int[] tmpArr, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        while (leftPos <= leftEnd && rightPos <= rightEnd){
            if (arr[leftPos] <= arr[rightPos])
                tmpArr[tmpPos++] = arr[leftPos++];
            else
                tmpArr[tmpPos++] = arr[rightPos++];
        }
        while (leftPos <= leftEnd)
            tmpArr[tmpPos++] = arr[leftPos++];
        while (rightPos <= rightEnd)
            tmpArr[tmpPos++] = arr[rightPos++];
        for (int i = 0; i < numElements; i++,rightEnd--){
            arr[rightEnd] = tmpArr[rightEnd];
        }
    }
}
